import math
from Vertice import Vertice

class Grafo:
    """
    Inicializa o grafo e seus vértices.
    Recebe uma lista de valores posicionados dos vértices.
    """
    def __init__(self,vertices):
        self.totalCelulas = len(vertices)
        self.vertices = self.addNodes(vertices, self.totalCelulas)
        self.ordem = int(math.sqrt(self.totalCelulas))
        self.ordemRegioes = int(math.sqrt(self.ordem))
        self.regioes = self.defineRegioes(self.totalCelulas, self.ordemRegioes, self.ordem)
        self.concatenaAdjacentes(self.ordem)
    
    def addNodes(self, listaVertices, numeroDeVertices):
        vertices = {}
        for i in range(numeroDeVertices):   
            vertices[i] = Vertice(i,listaVertices[i])       # Gera cada nó com um indice e label no tabuleiro (remetendo à cor também).
        return vertices

    def geraAdjacenciasNecessarias(self, vertice, adjacentes):
        for adjacente in adjacentes:
            if (vertice != adjacente):
                self.vertices[vertice].addAdjacente(self.vertices[adjacente])   # adiciona o vertice adjacente para a lista de vertices adjacentes
        self.vertices[vertice].calculaSaturacao()                               # calcula a saturacao do vertice


    def defineRegioes(self, numeroDeVertices, ordemRegioes, ordem):
        """
        Divide o tabuleiro em regiões.
        """
        regioes = []
        for primeiraRegiaoVertical in range (0, numeroDeVertices, ordemRegioes * ordem):                                   # percorre os quadros verticalmente
            for primeiraRegiaoHorizontal in range(primeiraRegiaoVertical, primeiraRegiaoVertical + ordem, ordemRegioes): # percorre os quadros horizontalmente
                regiao = set()
                for vertical in range(primeiraRegiaoHorizontal, primeiraRegiaoHorizontal + ordem * ordemRegioes - 1, ordem): # Percorre a região de forma vertical.
                    for horizontal in range(vertical, vertical + ordemRegioes):                                           # Percorre a região de forma horizontal.
                        regiao.add(horizontal)
                regioes.append(regiao)
        return regioes

    def defineVerticesDeMesmaLinha(self, indice, ordem):
        """
        Recebe o índice do vértice atual e a ordem do tabuleiro e retorna outros vértices existentes na mesma linha.
        """
        fimLinha = indice + (ordem - (indice % ordem)) # Especifica em qual índice a linha do vértice atual termina.
        inicioLinha = indice - (indice % ordem)        # Especifica em qual índice a linha do vértice atual começa.

        adjacentes = set()
        for i in range(inicioLinha, fimLinha):
            adjacentes.add(i)
        return adjacentes

    def defineVerticesDeMesmaColuna(self, indice, ordem):
        """
        Recebe o índice do vértice atual e a ordem do tabuleiro e retorna outros vértices existentes na mesma coluna.
        """
        adjacentes = set()
        for subindo in range(indice,0,-ordem):    # Percorre o índice atual ao início (0), reduzindo de 9 em 9 (se 9x9)
            adjacentes.add(subindo)
        for descendo in range(indice, self.totalCelulas, ordem): # Do índice atual ao fim pulando de 9 em 9 (se 9x9).
            adjacentes.add(descendo)                                # Percorre todos os vértices abaixo do vértice atual na mesma coluna.
        return adjacentes
    
    def defineVerticesNaMesmaRegiao(self, indice):
        """
        Percorre todas regiões para verificar se dado vértice está na região. Caso positivo, retorna a região.
        """
        for regiao in self.regioes:
            if indice in regiao:
                return regiao

    def concatenaAdjacentes(self, ordem):
        """
        Une todas as listas de diferentes tipos de adjacência (linha, coluna e região).
        """
        for vertice in self.vertices:
            adjacentesDeLinha = self.defineVerticesDeMesmaLinha(vertice, ordem)
            adjacentesDeColuna = self.defineVerticesDeMesmaColuna(vertice, ordem)
            adjacentesDeRegiao = self.defineVerticesNaMesmaRegiao(vertice)
            adjacentes = adjacentesDeLinha | adjacentesDeColuna | adjacentesDeRegiao
            self.geraAdjacenciasNecessarias(vertice, adjacentes)

    def verificaColoracaoDoGrafo(self):
        """
        Retorna se o grafo já está todo colorido ou não.
        """
        for vertice in self.vertices:
            if self.vertices[vertice].getLabel() == "":
                return False
        return True

    def getVerticeMaisSaturado(self):
        """
        Retorna aquele que é, atualmente, o vértice com maior grau de saturação.
        """
        maiorSaturacao = 0
        maiorIndice = 0
        for vertice in self.vertices:
            if self.vertices[vertice].getSaturacao() > maiorSaturacao and self.vertices[vertice].getLabel() == "":
                maiorSaturacao = self.vertices[vertice].getSaturacao()
                maiorIndice = vertice
        return maiorIndice

    def dSatur(self):
        """
        Algoritmo de coloração DSATUR.
        1. Atribua ao vértice de maior grau a cor de menor índice.
        2. Selecione o vértice com maior grau de saturação.
        3. Atribua ao vértice selecionado a cor de menor índice disponível.
        4. Se todos os vértices estiverem coloridos, pare. Caso contrário, retorne à etapa 3.
        """
        if self.verificaColoracaoDoGrafo():
            return True
        maiorSaturacao = self.getVerticeMaisSaturado()
        if self.vertices[maiorSaturacao].getPossibleColors(self.ordem) == -1 or not self.vertices[maiorSaturacao].getPossibleColors(self.ordem): # Sem mais cores possíveis.
            return False
        for cor in self.vertices[maiorSaturacao].getPossibleColors(self.ordem): # Obtém cores possíveis para colorir o vértice e aumentar o grau de saturação.
            self.vertices[maiorSaturacao].setLabel(cor)
            self.vertices[maiorSaturacao].aumentaSaturacaoAdjacentes()
            if self.dSatur(): # Repete o método.
                return True
            else: # Descolorir vértice caso o algoritmo executado por recursão retorne False.
                self.vertices[maiorSaturacao].diminuiSaturacaoAdjacentes()
                self.vertices[maiorSaturacao].setLabel("")
        return False